1. Field of the Invention
The field of the invention is computer graphics and digital imaging generally and more specifically the generation of surfaces that belong to a class of surfaces.
2. Description of the Prior Art
When an object can be described by means of dimensional coordinates, a second object can be described using the coordinates of a first object and a description of a transformation by means of which the coordinates of the first object can be transformed into coordinates describing the second object. FIG. 1 shows a simple example: curve 101 may be described by means of the coordinates of a set of points; shown are the points {a, b; c, d; e, f; g, h; i, j}. Curve 103 is described relative to curve 101 by the points {a+8,b;c+2,d;e, f;g+2,h;i+8,j}. It may also be described relative to curve 101 by means of the points of curve 101 and a vector field which describes the offsets that have to be added to the coordinates of the points making up curve 101 to obtain curve 103; for the points a,b through i,j, vector field 106 has the values (8,0), (2,0) , (0,0) , (2,0), (8,0) . As can be seen from the foregoing, vector field 106 is based on a correspondence between the points {a,b;c,d;e,f;g,h;i,j} of curve 101 and the points {a+8,b;c+2,d;e,f;g+2,h;i+8,j} of curve 103. In many cases, a vector field that describes how one object must be transformed to become a second object requires far fewer bits than a complete description of the second object, and vector fields are thus much used in computer graphics and digital imaging generally to save data storage space and/or network bandwidth.
When a vector field expresses a relationship between a first object and a second object, as it does with curves 101 and 103 of FIG. 1, the description of the first object and the vector field can be used to derive other objects that belong to a class of objects defined by the first object and the second object. In FIG. 1, three curves, 105, 107, and 109 are shown in dashed lines. These curves are different from, but clearly related to curves 101 and 103. In some sense, they have characteristics that are defined by the characteristics of curves 101 and 103. Each of the curves is generated by multiplying vector field A 106 by a fractional constant; with curve 105, the constant is xc2xe; with curve 106, it is xc2xd; with curve 109, it is xc2xc. It should be noted here that other curves that are related to curves 101 and 103 may be produced by multiplying vector field A 106 by constants whose values are outside the range [0,1].
Thus, in general, if one wants to generate a set of objects whose characteristics are defined by a first object and a second object, one can do so by making descriptions of the two objects, finding a vector field which, when applied to the first object, transforms the first object into an object that is similar to the second object, and then creating each object in the set of objects by manipulating the vector field and then applying the manipulated vector field to the first object to create the desired object. The technique is further not limited to two objects: the first object may have vector fields that describe transformations into a number of other objects, and objects belonging to the class defined by the first object and the other objects may be generated by combining the transformations specified in the vectors.
Objects generated by manipulating the vector field have many uses. For example, in image recognition systems, an image that is to be recognized must be compared with an example image; the image to be recognized is often a variation on the example image. For instance, the example image may be a photograph showing a smiling face; the image to be recognized may be frowning; by using vector fields as described above, the smiling face of the example image may be transformed into a frowning image and that image may be compared with the image to be recognized. Another use of such objects is what is termed xe2x80x9cmorphingxe2x80x9d, that is, a sequence of images such that a first image turns gradually into a second image. If one has a vector field which transforms the first image into the second image, the sequence of images required to morph the first image into the second image can be made by manipulating the vector field and applying the manipulated vector field to the first image. For example, the vector field manipulation of FIG. 1 could be seen as morphing the xe2x80x9cfrownxe2x80x9d of curve 101 into the xe2x80x9csmilexe2x80x9d of curve 103 via curves 109, 107, and 105.
The chief problem with generating sets of objects in this fashion is finding the vector field. One source of difficulty is automatically determining at all which vector field produces the xe2x80x9cbestxe2x80x9d family of objects, that is, produces the family of objects that makes the smoothest transition between the first object and the second object; another source of difficulty is the computational cost of such a determination.
Where the objects are images, the vector fields are termed optical flows. For details on optical flows, see J. L. Barron, et al., xe2x80x9cPerformance of optical flow techniquesxe2x80x9d, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 236-242, Champaign, Ill., 1992. Solutions for the problems of determining which vector field produces the best family of objects and for reducing the computational cost of such a determination when the objects are images are described in U.S. Pat. No. 5,745,668, Poggio, et al., Example-based image analysis and synthesis using pixelwise correspondence, issued Apr. 28, 1998, which is hereby incorporated by reference into the present patent application.
Images are, however, two-dimensional objects. Finding the best vector field with objects that are described using more than two dimensions presents further problems. In the following, an object that is described using more than two dimensions will be termed a surface. The problems of finding a vector field that can be applied to a given surface to generate members of a class of surfaces that is defined by two or more surfaces include the following:
finding a correspondence between the source and target objects upon which a vector field can be based that generates objects which preserves the characteristics of both the source surface and the target surface;
finding a way of quantifying correspondences between objects; and
finding a way to reduce the computational cost of finding the correspondences and thereby of finding the vector field.
It is an object of the present invention to overcome these problems and thereby make it possible to generate sets of surfaces that belong to a class defined by a first surface and one or more other surfaces from a description of the first surface and vector fields that describe how the first surface can be transformed into the other surfaces.
The problem of finding a correspondence is solved by defining the correspondence in terms of similarity to the target surface and amount of distortion of the source surface. In one aspect of the techniques, the distortion is measured by applying functions that measure structural changes to the source surface. In a preferred embodiment, the functions are directional spring functions for pairs of points in the source surface, the directional spring functions having the property that they respond to changes in distance and/or direction of the points relative to each other. In a further aspect of the techniques, the surfaces are represented by triangular meshes and the directional spring functions are applied to vertices that are adjacent to a given vertex in the triangular mesh and to any other vertex that is closer to the given vertex than the given vertex""s most distant adjacent vertex.
The computational cost of finding the correspondence is reduced by first producing pairs of increasingly simplified representations of the source surface and the target surface, the simplified representations having the property that they tend to preserve large-scale structural features of the source and target surfaces, and then using the pairs in order of decreasing simplification to find the correspondence. In a further aspect of this technique, a pair vector field found for each pair of simplified representations tends to preserve the features of both the pair""s source representation and the pair""s target representation. In another aspect, the pair vector field found for one pair is extended for the next less simplified pair and is used as the initial vector field in finding the pair vector field for the next less simplified pair. The least-simplified pair of representations are those for the original source surface and the original target surface and the pair vector field for the original source surface and the original target surface is the vector field for the original source surface and the original target surface.
The vector fields made using the foregoing techniques may be applied to a representation of the source surface to generate member surfaces of a class of surfaces which is defined by at least the source surface and the target surface.
Other objects and advantages will be apparent to those skilled in the arts to which the invention pertains upon perusal of the following Detailed Description and drawing, wherein: